package work1
// 8100*:现在纸币面额有 1元，2元，5元，10元，20元，50元和100元，
//  输入一个正整数的金额，输出所有的组成可能
//  比如输入 3元，则有  3个1元 和  一个2+1个1元两种可能;并统计组成的数量；
import scala.io.StdIn.readLine

object CoinCombinations {
  def main(args: Array[String]): Unit = {
    print("请输入金额：")
    val amount = readLine().toInt
    val denominations = List(100, 50, 20, 10, 5, 2, 1)
    val combinations = findCombinations(amount, denominations)
    println(s"总共有${combinations.length}种组合：")
    combinations.foreach(println)
  }

  def findCombinations(amount: Int, denominations: List[Int]): List[List[Int]] = {
    def helper(amount: Int, remaining: List[Int]): List[List[Int]] = {
      if (amount == 0) List(List())
      else if (amount < 0 || remaining.isEmpty) List()
      else {
        val withFirst = helper(amount - remaining.head, remaining).map(remaining.head +: _)
        val withoutFirst = helper(amount, remaining.tail)
        withFirst ++ withoutFirst
      }
    }
    helper(amount, denominations)
  }
}